package Algorithm.Sort.InsertSort;

public class Example {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 7, 9, 4, 1, 3, 6};
        int startIndex = getStartIndex(arr);
        sort(arr, startIndex);
        for(int i : arr){
            System.out.println(i);
        }
    }
    //获取起始索引(混乱区第一个值的索引)，从索引0开始，遵循从小到大原则的数组部分的最后一个元素)
    public static int getStartIndex(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            if(arr[i] > arr[i + 1]){
                return i + 1;
            }
        }
        return -1;
    }
    //根据传入的数组和起始索引进行插入排序
    public static void sort(int[] arr, int startIndex){
        //从起始索引开始循环，每循环一次，有序区增加一个元素，循环条件+1
        for(int i = startIndex; i < arr.length; i++){
            //从有序区最后一个元素开始(新增的)，进行选择排序
            for(int j = i; (j > 0 && arr[j] < arr[j-1]); j--){
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}
